package fun.coding.leetcode;

import java.util.HashMap;
import java.util.Map;

public class ClimbStairs {

	public static void main(String[] args) {
		ClimbStairs cs = new ClimbStairs();
		System.out.println(cs.climbStairs(2));
		System.out.println(cs.climbStairs(10));
	}
	
	public int climbStairs(int n) {
		Map<Integer, Integer> lookup = new HashMap<Integer, Integer>();
        lookup.put(1, 1);
      	lookup.put(2, 2);
		return climbHelper(n, lookup);
	}
	
	public int climbHelper(int n, Map<Integer, Integer> lookup) {
		if (lookup.containsKey(n)) return lookup.get(n);
        
        int res = climbHelper(n-1, lookup) + climbHelper(n-2, lookup);
        lookup.put(n, res);
        return res;
	}
	
	public int climbStairsDp(int n) {
		if (n < 1) return 0;
		if (n == 1) return 1;
		if (n == 2) return 2;
		
		// Could also save this array using fn = fn-1 + fn-2, and assign the values. 
		int[] a = new int[n + 1];
		a[1] = 1;
		a[2] = 2;
		
		for (int i = 3; i <= n; i++) {
			a[i] = a[i - 1] + a[i - 2];
		}
		
		return a[n];
	}
	
	// This will exceed time limit
	public int climbStairsRecursion(int n) {
        if (n == 1) return 1;
        
        if (n == 2) return 2;
        
        return climbStairsRecursion(n - 1) + climbStairsRecursion(n - 2);
	}

}
